// https://www.lintcode.com/problem/employee-importance/

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
public class Solution {
    /**
     * @param imput: 
     * @param id: 
     * @return: the total importance value 
     */
    public int getImportance(List<Employee> employees, int id) {
        // Write your code here.
        HashMap<Integer, Employee> map = new HashMap<>();
        for (int i = 0; i < employees.size(); ++i) {
            Employee employee = employees.get(i);
            map.put(employee.id, employee);
        }
        return search(map, id);
    }
    
    protected int search(HashMap<Integer, Employee> map, int id) {
        int ret = map.get(id).importance;
        List<Integer> subordinates = map.get(id).subordinates;
        for (int i = 0; i < subordinates.size(); ++i) {
            ret += search(map, subordinates.get(i));
        }
        return ret;
    }
}